This invention relates to memory addressing systems for manipulating arrays.
Array manipulations are common in data processing. For example, the time serial output signals from processors, especially array processors, often require reordering. A specific example of such an arrangement is cascaded Fast Fourier Transform (FFT) processors, which are cascaded to provide coarse and fine resolutions of frequency coefficients extracted from sample data in frequency surveillance or "zoom" systems.
The output signals from a first FFT processor are in bit-reversed order and are usually reordered for several reasons. For instance, in a step transform system, the successive output signals from the first FFT processor are processed diagonally by the second FFT processor. That is, the second FFT processor input signals are the first frequency coefficient in the first time frame, the second coefficient in the second time frame, and so on, from the first processor. The general input signal, n, to the second processor is the nth coefficient in the nth time frame from the first processor. The output signals from the first processor, whether in serial or parallel form, must be stored over successive time frames in order to provide the input signals to the second processor. The first complete set of input signals to the second processor is not available until n time frames have been sampled by the first processor.
Heretofore, a memory having n.sup.2 storage locations has been used to store the output signals from the first processor for reordering as input signals to the second processor. The invention described herein discloses a reordering memory system using only the minimum required memory size of n(n-1)/2 storage locations.